Skip to main content

binary tree

· One min read

node​

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return f'<{self.val},{self.left},{self.right}>'

array to tree​

def array_to_tree(arr):
    arr = [TreeNode(a) if a != None else None for a in arr]
    lng = len(arr)
    for i in range(lng):
        if arr[i]:
            if 2*i+2 < lng:
                arr[i].right = arr[2*i+2]
                arr[i].left = arr[2*i+1]
            elif 2*i+1 < lng:
                arr[i].left = arr[2*i+1]
    return arr[0]

3 DFS traversals​

  • preorder
  • inorder
  • psotorder
class DFS:
    def trv_preorder(self, node):
        this_method = self.get_method()
        if node:
            return [node.val] + this_method(node.left) + this_method(node.right)
        else:
            return [None]

    def trv_inorder(self, node):
        this_method = self.get_method()
        if node:
            return this_method(node.left) + [node.val] + this_method(node.right)
        else:
            return [None]

    def trv_postorder(self, node):
        this_method = self.get_method()
        if node:
            return this_method(node.left) + this_method(node.right) + [node.val]
        else:
            return [None]

    def get_method(self):
        import inspect
        level = 1
        for m in inspect.getmembers(self, predicate=inspect.ismethod):
            if m[0] == inspect.stack()[level][3]:
                return m[1]
        raise LookupError